'''
https://leetcode.cn/problems/word-break/description/
'''
from collections import deque
from typing import List

class Node:
    def __init__(self):
        self.ended = None
        self.next = {}

class Solution:

    def insert(self, word):
        cur = self.root
        for c in word:
            if c not in cur.next:
                cur.next[c] = Node()
            cur = cur.next[c]
        cur.ended = word

    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        self.root = Node()
        for word in wordDict:
            self.insert(word)
        n = len(s)

        path = deque()
        res = []
        def f(l):
            if l == n:
                res.append(' '.join(path))
                return
            cur = self.root
            for r in range(l, n):
                if s[r] not in cur.next:
                    break
                cur = cur.next[s[r]]
                if not cur.ended:
                    continue
                path.append(cur.ended)
                f(r + 1)
                path.pop()
        f(0)
        return res

s = "catsanddog"
wordDict = ["cat","cats","and","sand","dog"]
res = Solution().wordBreak(s, wordDict)
print(res)